package com.xzz.window;

import java.util.TreeSet;

/**
 * @author: hhz
 * @create: 2022-01-19 11:24
 * 220. 存在重复元素 III
 * 给你一个整数数组 nums 和两个整数k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 *
 * 如果存在则返回 true，不存在返回 false。
 *
 **/
public class ContainsNearbyAlmostDuplicate {
    public static void main(String[] args) {
        System.out.println(containsNearbyAlmostDuplicate(new int[]{1,2,3,1},3,0));
        System.out.println(containsNearbyAlmostDuplicate(new int[]{1,0,1,1},1,2));
        System.out.println(containsNearbyAlmostDuplicate(new int[]{1,5,9,1,5,9},2,3));

        System.out.println(containsNearbyAlmostDuplicate(new int[]{8,7,15,1,6,1,9,15},1,3));
    }
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> window = new TreeSet<>();
        int left = 0;
        int right = 0;
        while (right<nums.length){
            long num = nums[right];
            right++;
            //小于等于num的最大元素
            Long floor = window.floor(num);
            //大于等于num的最小元素
            Long ceiling = window.ceiling(num);
            if(floor!=null && num-floor<=t){
                return true;
            }
            if(ceiling!=null && ceiling-num<=t){
                return true;
            }
            window.add(num);
            while (right-left>k){
                window.remove((long)nums[left]);
                left++;
            }
        }
        return false;
    }
}
